As information society advances, services based on information networks, such as electronic settlement and a basic resident register network are expected to be in widespread use. Information security techniques are essential to operate safely these services. Public key cryptosystems are used as a fundamental technology. A variety of public key cryptosystems are known. One of the main schemes is elliptic curve cryptography. Using the public key cryptosystem, services such as encryption, digital signature, and authentication function are used, and private information is protected from unauthorized accessing by a third party.
Smart cards are known as a device of a user in the services such as the electronic settlement and the basic resident register network. The smart card is a card having an integrated circuit (IC) chip. Private information of the user is stored on a memory area of the smart card. The IC chip of the smart card is provided with functions of encryption, digital signature, and authentication. When a process of these function is executed, the private information of the user is used as a key. Since the private information of the user is stored on the memory area of the card, the IC card is expected to dramatically increase security (tamper-resistance property) against unauthorized browsing by a third party.
However, weakness of the tamper resistance property of the smart card has been recognized since an analysis method called power analysis (PA) was found in 1998. The smart card performs an encryption process using the user private information as a key. The PA measures power consumption of the smart card in the middle of an encryption process, and then estimates and analyzes the user private information using the measured data.
The PA is known as a powerful analysis method. The necessity for a protective step against the PA has been described in a variety of international standards. For example, ISO15408 as the international security standard specifies in a protection profile (PP) for smart card that a step against the PA be essential. Since a PA attack is an attack to observe power, an attack target is not limited to the smart card. A PA is known which measures an electromagnetic wave generated by a personal digital assistant (PDA) that consumes power. The attack target of the PA can be any of the devices that consume power.
Some of the basics of the elliptic curve cryptography in the public key cryptosystem are described below, and how the PA is embodied is also described below.
Elliptic Curve Cryptography
Elliptic curve cryptography is encryption that uses computation of a rational point on an elliptic curve as illustrated in FIG. 1. Two elements, namely, a prime case and binary case, exist in an elliptic curve. Using two parameters, a and b, each element is described in the equations described below.Prime case: y2=x3+ax+b(mod p)(x,y,a,bεGF(p), p: prime case) andbinary case: y2+yx=x3+ax2+b(mod f(x))(x,y,a,bεGF(2m), f(x): m-th order irreducible polynomial)
The elliptic curve of an prime case is described below, and this discussion is also equally applicable to an elliptic curve of the binary case.
A rational point on the elliptic curve is a set of (x,y) satisfying a relational equation of the elliptic curve. In the elliptic curve, two types of computations are defined, namely, an “addition of points” and a “doubling of point.” A point is expressed by an affine representation based on a two-dimensional vector (x,y), and a representation (projective coordinates or Jacobian coordinates) based on a three-dimensional vector (X,Y,Z).
FIG. 2 illustrates an addition of two points, point P and point Q on the elliptic curve. Point R resulting from adding point P and point Q is defined as described below. A vertical line is drawn passing through the intersection of a line connecting point P and Point Q and the elliptic curve, and the intersection of the vertical line and the elliptic curve is defined as point R. In the addition of points on the elliptic curve, the commutative law (A+B=B+A) holds as in the standard integer addition. If a Z coordinate of one of the two points is 1 in the addition of points on the three dimensional vector representation, speed-up of the addition is possible. The subtraction of the points is also defined by P=R−Q. More specifically, a vertical line passing through point R is drawn, and a line connecting the intersection of the vertical line and the elliptic curve and point Q is drawn. The intersection of the line and the elliptic curve becomes point P.
A calculation process of the addition of points in the Jacobian coordinates is well known. As illustrated in detail in FIG. 3, steps 800 through 835 are performed to perform addition R of point A and point B on a prime case, R=ECADD(A,B)=A+B. It is noted that ECDBL(A)=A+A. Although the detailed discussion of the addition points in the Jacobian coordinates is omitted here, it is understood that the addition of points and the subtraction of points take more time than the addition and subtraction of integers.
FIG. 4 illustrates the doubling of point P on the elliptic curve. The doubling of point P is defined as below. A line tangent to point P on the elliptic curve is drawn, and a vertical line passing through the intersection of the tangential line and the elliptic curve is drawn. The intersection of the vertical line and the elliptic curve is defined as result R of the doubling operation.
FIGS. 5A and 5B illustrate a negative point and a point at infinity. As illustrated in FIG. 5A, a vertical line passing through point P is drawn, and the intersection of the vertical line and the elliptic curve is defined as the negative point “−P” of point P on the elliptic curve. Referring to FIG. 5B, the point at infinity is defined as the intersection of the line connecting point P and point −P and the elliptic curve. The infinity point O has the same property as that of zero in the addition of ordinary integers, i.e., A+O=O+A=A and 2O=O hold.
In the elliptic curve cryptography, an arithmetic operation using elliptic scalar multiplication of point is performed. The scalar multiplication of point is an operation to calculate point V on the elliptic curve satisfying V=xA where point A is on the elliptic curve and x is an integer called a scalar value, and represents private information. The scalar d multiplication of point A, if plotted in the same way as in FIGS. 1, 2, 4, and 5A and 5B, is illustrated in FIG. 6. More specifically, the scalar multiplication of point is performed based on the addition and doubling of points described above. In the case of the elliptic curve Diffie Hellman (ECDH) key exchange, a point on the elliptic curve serving as a public key of a communication partner is A, and a private key is d.
Secure key sharing is implemented by calculating point V on the elliptic curve satisfying V=dA. A third party not knowing the value of the private key d has difficulty in calculating the value of a correct public key. Here, d is the private key, and has a value that should not be leaked to a third party such as an attacker. The protection of the value of d is an important tamper resistance function. Even if the values other than d (i.e., A and V) are known, a calculation amount of d is too large mathematically. It is very difficult to solve d within the practical time scale (this is called the discrete logarithm problem). More specifically, if an elliptic curve parameter is 160 bits or larger, the value of d is difficult to solve even if the values of A and V are known.
The private key d is mathematically difficult to solve in this way, but the use of the PA allows the private key to be easily deciphered. The basic mechanism of the PA is closely related to the process step of the scalar multiplication of point. It is thus known that the use of the PA allows d to be deciphered bit by bit.
The d multiplication point V of point A on the elliptic curve (=dA) is calculated using the addition of points and the doubling of point described above. Such a calculation technique is not limited to the arithmetic operation on the elliptic curve but may find a variety of applications. More specifically, a binary method, a window method, and a comb window method are known. A scalar multiplication using the window method and the comb-type window method is described below.
FIG. 7 illustrates an algorithm of the elliptic scalar multiplication using the window method. Here, A=dG is determined based on point G on the elliptic curve and a scalar value d (having a 12-bit width). A window width of the window method is 3 bits, and the number of elements in a window table is 23=8. More specifically, 0G=O (zero point) is mapped to an index value “000,” 20G is mapped to an index value “001,” 21G is mapped to an index value “010,” 21G+20G is mapped to an index value “011,” 22G is mapped to an index value “100,” 22G+20G is mapped to an index value “101,” 22G+21G is mapped to an index value “110,” and 22G+21G+20G is mapped to an index value “111.”
An actual arithmetic operation of using such a window table is described below. A table value of the window table is read according to upper 3 bits of d as an index value in step (1). The read table value is substituted for a variable A. More specifically, (1) A=Tab[d11,d10,d9] (Tab[x] represents a table value specified by [x]).
In step (2), 23A is calculated in response to 3 bits as a shift width of the window, i.e., (2)A=23A. In step (3), a table value is read from the window table according to next 3 bits of d as an index, and the read table value is added to A. Step (3) is expressed as (3) A=A+Tab[d8,d7,d6]. In step (4), 23A is calculated in response to 3 bits as a shift width of the window. Step (4) is thus expressed as (4) A=23A. In step (5), a table value is read from the window table according to next 3 bits of d as an index, and the read table value is added to A. Step (5) is expressed as (5) A=A+Tab[d5,d4,d3].
In step (6), 23A is calculated in response to 3 bits as a shift width of the window. Step (6) is thus (6) A=23A. Finally, in step (7), a table value is read from the window table according to next 3 bits of d as an index, and the read table value is added to A. Step (7) is expressed as (7) A=A+Tab[d2,d1,d0]=dG.
FIG. 8 illustrates a specific example of d=(101011101001)2. The window table remains unchanged. In step (1), a table value is read from the window table according to the upper 3 bits “101” of d as an index. The read table value is substituted for the variable A. Step (1) is expressed as (1)A=Tab[101]=(22+20)G.
In step (2), 23A is calculated in response to 3 bits as a window width. Step (2) is expressed as (2)A=23A=(25+23)G. In step (3), a table value is read from the window table according to the next 3 bits “011” as an index, and the read value is added to A. Step (3) is expressed as (3) A=A+Tab[011]=(25+23+21+20)G. In step (4), 23A is calculated in response to the next 3 bits as a window width. Step (4) is expressed as (4)A=23A=(28+26+24+23)G.
In step (5), a table value is read from the window table according to the next 3 bits “101” as an index, and the read value is added to A. Step (5) is expressed as (5) A=A+Tab[101]=(28+26+24+23+22+20)G. In step (6), 23A is calculated in response to 3 bits as a window width. In Step (6) is expressed as (6) A=23A=(211+29+27+26+25+23)G. In step (7), a table value is read from the window table according to the next 3 bits “001” as an index, and the read value is added to A. Step (7) is expressed as (7) A=A+Tab[101]=(211+29+27+36+25+23+20)G.
The scalar multiplication using the comb-type window method is described with reference to FIG. 9. As the name suggests, a comb-type window is set in the comb-type window method. In the standard window method, the table value) “(22+21+20)G” mapped to an index value “111” is consecutive. In the comb-type window method, discrete values are registered in the window table. More specifically, 0G=O (zero point) is mapped to an index value “000,” 20G is mapped to an index value “001,” 24G is mapped to an index value “010,” 24G+20G is mapped to an index value “011,” 28G is mapped to an index value “100,” 28G+20G is mapped to an index value “101,” 28G+24G is mapped to an index value “110,” and 28G+24G+20G is mapped to an index value “111.”
The specific calculation process steps using such a window table are described below. The 23 multiplication calculation should be performed in the window method while the doubling calculation is advantageously sufficient in the comb-type window method. The number of doubling calculations of points in the elliptic scalar multiplication is reduced to one-third. Generally, in the comb-type window method having a k-bit window width, the number of doubling operations is reduced to 1/k.
In step (1), a table value of the window table is read according to 3 bits of d every 4 bits as an index value in step (1). The read table value is substituted for a variable A. More specifically, step (1) is expressed as (1) A=Tab[d11,d7,d3]. In step (2), 2A is calculated in response to 1 bit as a shift width of the window, i.e., step (2) is expressed as (2)A=2A. In step (3), a table value is read from the window table according to an index value in which the index value is the next 3 bits obtained by right shifting by 1 bit the window from the state of step (1). The read table value is added to A. Step (3) is expressed as (3) A=A+Tab[d10,d6,d2]. In step (4), 2A is calculated in response to a 1-bit window shift width. Step (4) is expressed as (4) A=2A.
In step (5), a table value is read from the window table according to an index value in which the index value is the next 3 bits obtained by right shifting by 1 bit the window from the state of step (3). The read table value is added to A. Step (5) is expressed as (5) A=A+Tab[d9,d5,d1]. In step (6), 2A is calculated in response to a 1-bit window shift width. Step (6) is expressed as (6)A=2A. Finally, in step (7), a table value is read from the window table according to an index value in which the index value is the next 3 bits obtained by right shifting by 1 bit the window from the state of step (5). The read table value is added to A. Step (7) is expressed as (7) A=A+Tab[d8,d4,d0]=dGo.
FIG. 10 illustrates a specific example of d=(101011101001)2. The window table remains unchanged. In step (1), a table value is read from the window table according to 3 bits “111” read from d from the most significant bit on a per 3-bit basis. The read table value is substituted for the variable A. Step (1) is thus expressed as (1) A=Tab[111]=(28+24+20)G.
In step (2), 2A is calculated in response to a 1-bit window shift width. Step (2) is expressed as (2)A=A2A=(29+25+21)G. In step (3), a table value is read from the window table according to an index value in which the index value is the next 3 bits “010” obtained by right shifting by 1 bit the window from the state of step (1). The read table value is added to A. Step (3) is expressed as (3) A=A+Tab[010]=(29+25+24+21)G. In step (4), 2A is calculated in response to a 1-bit window shift width. Step (4) is expressed as (4)=2A=(210+26+27+25+22).
In step (5), a table value is read from the window table according to an index value in which the index value is the next 3 bits “110” obtained by right shifting by 1 bit the window from the state of step (3). The read table value is added to A. Step (5) is expressed as (5) A=A+Tab[110]=(210+28+26+35+24+22). In step (6), 2A is calculated in response to a 1-bit window shift width. Step (6) is expressed as (6) A=2A=(211+29+27+36+25+23)G. Finally, in step (7), a table value is read from the window table according to an index value in which the index value is the next 3 bits “001” obtained by right shifting by 1 bit the window from the state of step (5). The read table value is added to A. Step (7) is expressed as (7) A=A+Tab[001]=(211+29+27+26+25+23+20G=dG. The same result as that of FIG. 8 is thus obtained.
In the above-described comb-type window method, a single window table is used. A fast comb-type window method is available which speeds up the process by reducing even further the number of doubling operations with two window tables used in place of increasing an area of a storage table. Such the comb-type window method is discussed below with reference to FIGS. 11A and 11B.
An upper table for an upper half bit block of d and a lower table for a lower half bit block of d are prepared in such a comb-type window method. In the discussion that follows, d is 18 bits. More specifically, in the upper table, 0G=O (zero point) is mapped to an index value “000,” 29G is mapped to an index value “001,” 212G is mapped to an index value “010,” 212G+29G is mapped to an index value “011,” 215G is mapped to an index value “100,” 215G+29G is mapped to an index value “101,” 215G+212G is mapped to an index value “110,” and 215G+212G+29G is mapped to an index value “111.”
On the other hand, in the lower table, 0G=O (zero point) is mapped to an index value “000,” 20G is mapped to an index value “001,” 23G is mapped to an index value “010,” 23G+20G is mapped to an index value “011,” 26G is mapped to an index value “100,” 26G+20G is mapped to an index value “101,” 26G+23G is mapped to an index value “110,” and 26G+23G+20G is mapped to an index value “111.”
The arithmetic operation using the window table is specifically discussed as below. In step (1), 3 bits of the upper half bit block are extracted as an index value every 3 bits, and a table value is read from the upper table according to the index value. The read table value is substituted for the variable A. Step (1) is expressed as (1) A=TabH[d17, d14, d11]. TabH represents a table value of the upper table. In step (2), 3 bits of the lower half bit block are extracted as an index value every 3 bits, and a table value is read from the lower table according to the index value. The read table value is added to the variable A. Step (2) is expressed as (2) A=A+TabL[d8, d5, d2]. TabL represents a table value of the lower table.
In step (3), 2A is calculated in response to a 1-bit table shift width. Step (3) is expressed as (3)A=2A. In step (4), next 3 bits of the upper half bit block is extracted as an index value by right shifting the window from the state of step (1) by 1 bit, and a table value is read from the upper table according to the index value. The read table value is added to A. Step (4) is expressed as (4)=A+TabH[d16, d13, d10]. In step (5), next 3 bits of the lower half bit block is extracted as an index value by right shifting the window from the state of step (2) by 1 bit, and a table value is read from the lower table according to the index value. The read table value is added to A. Step (5) is expressed as (5)=A+TabL[d7, d4, d1]. In step (6), 2A is calculated in response to a 1-bit table shift width. Step (6) is expressed as (6)A=2A.
In step (7), next 3 bits of the upper half bit block is extracted as an index value by right shifting the window from the state of step (4) by 1 bit, and a table value is read from the upper table according to the index value. The read table value is added to A. Step (7) is expressed as (7)=A+TabH[d15, d12, d9]. In step (8), next 3 bits of the lower half bit block is extracted as an index value by right shifting the window from the state of step (5) by 1 bit, and a table value is read from the lower table according to the index value. The read table value is added to A. Step (8) is expressed as (8)=A+TabL[d6, d3, d0]=dG.
The bit length becomes longer than the bit length of d in FIG. 9. In contrast to the 3-bit width of FIG. 9, the window table having a 6-bit length is used. The number of doubling operations is reduced.
In the window method and the comb-type window method, the table value is O (infinity point) in response to an index value of “000” in the window table. The measured power consumption of a device executing the scalar multiplication is diagrammatically illustrated in FIGS. 12A and 12B. If the index value is non-zero (C=A+B), a waveform of FIG. 12A is obtained, and if the index value is zero, a waveform of FIG. 12B (C=A+O) is obtained. Distinctively different waveforms result. This is because a special arithmetic operation is performed in the addition to O point. The power consumption waveform contributes to a leakage of information that a partial bit value of d as the private information is 0.
A mathematical algorithm that deciphers all the bits of the private key d using the partial bit value of “0” of d is known. It is also known that if the scalar multiplication is used in digital signature generation, a private key for digital signature leaks.
It is thus extremely important that any of the bits of d as the private key should not be leaked in the calculation of A=dG.
A digital signature generation method of using the elliptic curve digital signature algorithm (ECDSA) is known as a typical process of the elliptic curve cryptography based on the elliptic scalar multiplication. FIG. 13 illustrates an algorithm of this process. This process outputs hi, and signature data (ui,vi) by performing a calculation process including receiving a private key s for signature, and signature target data hi, generating a temporary random number di, and performing an elliptic scalar multiplication diG (G is called a base point and is publicly disclosed). Here, i is a variable representing the number of processes for signature generation, r represents a publicly disclosed prime number, and di−1 is an integer satisfying di−1×di=1 (mod r).
ECDSA signature may be applied to a device such as a smart card, and the private key s for signature and the temporary random number di are not observed from the outside. The private key s for signature is a particularly important information resource, and must be strictly protected. However, if an attacker has successfully collected a large number of data units of several upper bits or lower bits of the temporary random number di using the attack method proposed by Howgrave-Graham et al. as illustrated in FIG. 14, the private key s for signature can be deciphered by combining the collected data and data hi and (ui,vi) output to the outside.
The value of the temporary random number di cannot be observed from the outside. If an attacker having the SPA (simple PA) capability uses the SPA while the elliptic scalar multiplication diG is performed, the most significant bits or the least significant bits of the temporary random number di can be deciphered. If the results are combined with the attack method proposed by Howgrave-Graham et al., the attacker can decipher the private key s. In view of such a combined attack, it is essential that not even one bit of the information related to the temporary random number di be leaked even if the SPA is applied to the calculation of diG.
To prevent the value of d as the secret information from being leaked, the power consumption waveforms for the non-zero index value (C=A+B) and the zero index value (C=A+O) are set to be identical to each other such that the attacker cannot differentiate the two waveforms. Available as such a technique is the dummy operation technique proposed by Coron et al. FIG. 15 diagrammatically illustrates the dummy operation technique in the comb-type window method. The basic operation of the dummy operation technique is identical to the operation discussed with reference to FIG. 9. In the dummy operation technique, except step (1), a process step is performed to determine whether an index value, if determined from d, is “000.” If the index value of the table is “000,” a non-zero table value is added to a variable B for dummy rather than to the variable A to which the non-table value is to be otherwise added. If the index value is “000” (a value other than “000” may also acceptable) in each of steps (3), (5) and (7) as illustrated in FIG. 15, the sum of A and a table value responsive to an index value of “001” is stored. In this way, the power consumption waveform responsive to the index value of “000” is set to be equal to the waveform for the non-zero value. The leakage of the private information d is prevented.
The dummy operation technique protects the private information d against the PA, and causes no increase in the amount of calculation in comparison with the case where no PA resistance mode is incorporated. However, the dummy variable B is needed. Since the dummy operation needs to be performed not to destroy interim data stored as the variable A, the variable B is thus stored on an area separate from that of the variable A. If no PA resistance mode is incorporated, a storage area (random-access memory: RAM) for only the variable A is needed. The dummy operation needs a RAM storing the variable A and the variable B. In other words, double RAMs are needed. The RAM resource of the smart card is typically limited in comparison with the ROM resource. It is very important to reduce the capacity requirement for the RAM.